// https://leetcode-cn.com/problems/subsets/
// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
// 输入：nums = [1,2,3]
// 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
// 【这题存在特殊性：求所有数的集合】
#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

class Solution {
public:
	// 暴力枚举法 但是速度很快，时间击败100% ，内存击败94.15%
    vector<vector<int>> subsets(vector<int>& nums) {
		vector<vector<int>> res;	
		const int len = nums.size();
		for(int i = 0; i < 1 << len; i++){
			// 获取下标
			bitset<10> bi(i); // 注意：这里必须是常量，bitset<len>的方式是错误的，大概原因应该是编译期间确定数值类型导致的
			vector<int> tmp;
			for(int j = 0; j < len; j++){
				if(bi[j] == 1){
					tmp.push_back(nums[j]);
				}
			}
			res.push_back(tmp);
			
		}
		return res;
    }
	
	// 动态规划 基础思想就是新的集合 = 原集合 + (原集合的每个元素+新的元素) + 新的元素
	// 1 
	// 1 2 1,2
	// 1 2 1,2 3 1,3 2,3 1,2,3 
	vector<vector<int>> subsets1(vector<int>& nums) {
		vector<vector<int>> res;	
		const int len = nums.size();
		for(int i = 0; i < len; i++){
			vector<vector<int>> tmp = dp(nums[i], res);
			for(auto item : tmp){
				res.push_back(item);
			}
		}
		res.push_back({});
		return res;
    }
	
	vector<vector<int>> dp(int index, vector<vector<int>> res){
		vector<vector<int>> tmp;
		if(res.size() > 0){
			for(auto item : res){
				// vector<int> tmpItem;
				// tmpItem.assign(item.begin(), item.end());
				item.push_back(index);
				tmp.push_back(item);
			}
		}
		
		tmp.push_back({index});
		return tmp;
	}
};

int main(){
	vector<int> nums = {1,2,3};
	Solution so;
	auto res = so.subsets(nums);
	
	for(auto item : res){
		for(auto i : item){
			cout << i << ",";
		}
		cout << endl;
	}
	
	return 1;
}